#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <memory>
#include <algorithm>
#include <numeric>

using namespace std;

// 位1的个数
class Solution
{
public:
    int hammingWeight(int n)
    {
        int ans = 0;
        while (n)
        {
            n &= (n - 1);
            ans++;
        }
        return ans;
    }
};

// 腐烂的橘子
class Solution
{
public:
    int m, n;
    bool vis[11][11];
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int orangesRotting(vector<vector<int>> &grid)
    {
        m = grid.size(), n = grid[0].size();
        int freshCount = 0, ans = 0;
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1)
                {
                    freshCount++;
                }
                else if (grid[i][j] == 2)
                {
                    q.push({i, j});
                }
            }
        }
        while (q.size())
        {
            // 记录当前这一轮的数量
            int size = q.size();
            for (int i = 0; i < size; i++)
            {
                auto [a, b] = q.front();
                q.pop();
                for (int k = 0; k < 4; k++)
                {
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)
                    {
                        q.push({x, y});
                        vis[x][y] = true;
                        freshCount--;
                    }
                }
            }
            // 如果有橘子加入到队列中，说明有橘子腐烂
            if (q.size())
            {
                ans++;
            }
        }
        if (freshCount > 0)
            return -1;
        return ans;
    }
};

// 判断是否为二叉搜索树
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution
{
public:
    bool isValidBST(TreeNode *root)
    {
        stack<TreeNode *> st;
        long long inorder = (long long)INT_MIN - 1;
        while (st.size() || root)
        {
            while (root)
            {
                st.push(root);
                root = root->left;
            }
            root = st.top();
            st.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root->val <= inorder)
                return false;
            inorder = root->val;
            root = root->right;
        }
        return true;
    }
};

class Solution
{
public:
    vector<long long> v;
    bool isValidBST(TreeNode *root)
    {
        dfs(root);
        long long inorder = (long long)INT_MIN - 1;
        for (auto x : v)
        {
            if (x <= inorder)
                return false;
            inorder = x;
        }
        return true;
    }

    void dfs(TreeNode *root)
    {
        if (root == nullptr)
            return;
        dfs(root->left);
        v.push_back(root->val);
        dfs(root->right);
    }
};

// 岛屿的最大面积
class Solution
{
public:
    int m, n;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool vis[51][51];
    int maxAreaOfIsland(vector<vector<int>> &grid)
    {
        int ans = 0;
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1 && !vis[i][j])
                {
                    ans = max(ans, bfs(grid, i, j));
                }
            }
        }

        return ans;
    }

    int bfs(vector<vector<int>> &grid, int i, int j)
    {
        queue<pair<int, int>> q;
        q.push({i, j});
        vis[i][j] = true;

        int count = 1;
        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)
                {
                    q.push({x, y});
                    vis[x][y] = true;
                    count++;
                }
            }
        }

        return count;
    }
};

class Solution
{
public:
    int m, n, count;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool vis[51][51];
    int maxAreaOfIsland(vector<vector<int>> &grid)
    {
        int ans = 0;
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1 && !vis[i][j])
                {
                    count = 0;
                    dfs(grid, i, j);
                    ans = max(ans, count);
                }
            }
        }

        return ans;
    }

    void dfs(vector<vector<int>> &grid, int i, int j)
    {
        count++;
        vis[i][j] = true;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1)
            {
                dfs(grid, x, y);
            }
        }
    }
};

// 计算器
class Solution
{
public:
    int calculate(string s)
    {
        vector<int> stk;
        char preSign = '+';
        int n = s.size(), num = 0;
        for (int i = 0; i < n; i++)
        {
            if (isdigit(s[i]))
            {
                num = num * 10 + int(s[i] - '0');
            }
            if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1)
            {
                switch (preSign)
                {
                case '+':
                    stk.push_back(num);
                    break;
                case '-':
                    stk.push_back(-num);
                    break;
                case '*':
                    stk.back() *= num;
                    break;
                default:
                    stk.back() /= num;
                }
                preSign = s[i];
                num = 0;
            }
        }
        return accumulate(stk.begin(), stk.end(), 0);
    }
};
